package main

import "fmt"

type TreeNode struct {
	Value       int
	Left, Right *TreeNode
}

// 前序遍历：根节点 -> 左子树 -> 右子树
func preorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}

	fmt.Printf("%d ", root.Value) // 打印当前节点的值
	preorderTraversal(root.Left)  // 递归遍历左子树
	preorderTraversal(root.Right) // 递归遍历右子树
}

// 中序遍历：左子树 -> 根节点 -> 右子树
func inorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}

	inorderTraversal(root.Left)   // 递归遍历左子树
	fmt.Printf("%d ", root.Value) // 打印当前节点的值
	inorderTraversal(root.Right)  // 递归遍历右子树
}

// 后序遍历：左子树 -> 右子树 -> 根节点
func postorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}

	postorderTraversal(root.Left)  // 递归遍历左子树
	postorderTraversal(root.Right) // 递归遍历右子树
	fmt.Printf("%d ", root.Value)  // 打印当前节点的值
}

func main() {
	// 创建一个二叉树
	root := &TreeNode{
		Value: 1,
		Left: &TreeNode{
			Value: 2,
			Left: &TreeNode{
				Value: 4,
			},
			Right: &TreeNode{
				Value: 5,
			},
		},
		Right: &TreeNode{
			Value: 3,
			Left: &TreeNode{
				Value: 6,
			},
			Right: &TreeNode{
				Value: 7,
			},
		},
	}

	// 前序遍历
	fmt.Println("Preorder Traversal:")
	preorderTraversal(root)
	fmt.Println()

	// 中序遍历
	fmt.Println("Inorder Traversal:")
	inorderTraversal(root)
	fmt.Println()

	// 后序遍历
	fmt.Println("Postorder Traversal:")
	postorderTraversal(root)
	fmt.Println()
}
